//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 353 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;

public class ZuiXiaoDeKgeShuLcof {
    public static void main(String[] args) {
        Solution solution = new ZuiXiaoDeKgeShuLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 维护一个长度为k的大顶堆
         * 时间复杂度为nlogk，空间复杂度为k
         * 遍历数组需要时间为n，调整堆需要时间为logk
         * 这种方式适用于n较大且k较小的场景
         */
        public int[] getLeastNumbers1(int[] arr, int k) {
            if (k == 0 || arr.length == 0) return new int[]{};
            if (k >= arr.length) return arr;
            PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> { return b - a; });
            for (int num : arr){
                if (queue.size() < k) queue.add(num);
                else if (queue.peek() > num) {
                    queue.poll();
                    queue.add(num);
                }
            }
            return queue.stream().mapToInt(Integer::intValue).toArray();
        }

        /**
         * 基于快速排序的思想对数组进行修改，时间复杂度为N,空间复杂度为logN（递归深度）
         */
        public int[] getLeastNumbers(int[] arr, int k) {
            if (k >= arr.length) return arr;
            return quickSort(arr,0,arr.length - 1, k);
        }

        /**
         * 并不是真正的快排，没有保证顺序
         */
        public int[] quickSort(int[] arr, int left, int right, int k){
            int l = left;
            int r = right;
            while (l < r){
                // 哨兵为数组第一个位置的值，此时一定要先从右向左找
                // 如果从左向右，可能会出现l = r的情况，导致交换失败，例如：5...6
                while (l < r && arr[r] >= arr[left]) r--;// 在右边找比哨兵小的值
                while (l < r && arr[l] <= arr[left]) l++;// 在左边找比哨兵大的值
                swap(arr, l, r);// 根据哨兵交换所有值
            }
            swap(arr, l, left);// 交换哨兵，此时l处左边值均小于l处的值
            if (l > k) return quickSort(arr, left, l - 1, k);// 此时说明左边数量太多
            if (l < k) return quickSort(arr, l + 1, right, k);// 此时说明左边数量不够
            return Arrays.copyOf(arr, k);// 如果l处索引为k，说明恰好可以返回
        }
        public void swap(int[] arr, int i, int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}